The invention relates to electronic devices, and, more particularly, to encoders and decoders for turbo codes and methods of coding.
Digital communication systems typically employ a channel coding for the symbols transmitted across a communication channel; the channel coding introduces redundancies to provide for correction of errors introduced by the communication channel. In 1993 Berrou et al introduced xe2x80x9cturbo codingxe2x80x9d as a type of channel coding with error correction performance close to the theoretical limit. Turbo code are parallel concatenations of recursive systematic (punctured) convolutional coders with random interleaving between the recursive encoders as illustrated schematically in FIG. 2a for the case of two recursive encoders. FIG. 2b shows a corresponding decoder with serial architecture; parallel decoders also exist. Turbo codes apparently achieve their performance with relatively simple component codes and large information blocks with random interleavers. A signal-to-noise ratio of only 0.7 dB could yield a bit error rate (BER) of 10xe2x88x925 and could be useful for noisy communication channels. Essentially, the interleaver should be capable of spreading low-weight input sequences so that the resulting codeword has high weight. The interleaver reorders the symbols in a block of K symbols (typically in the range of 100-100,000). Mathematically, the interleaver generates a permutation that maps the set {0, 1, 2, 3, . . . , Kxe2x88x921} onto itself so that the mapping is one-to-one.
In conventional communication systems that require interleaving, the common practice is to apply a block interleaver. A block interleaver can be easily implemented by writing the data into a matrix of dimensions K1xc3x97K2 (K=K1K2) row by row and then reading the data out column by column.
The actual permutation used in a turbo coding scheme has a crucial effect on the performance of the coding scheme in terms of probability of bit error at a given signal-to-noise ratio. It has been found that a good interleaver for a turbo coding scheme resembles a random permutation. The simple method of using a block interleaver has been proven to be unsatisfactory for turbo coding.
The design of a good interleaver for a turbo coding scheme turned out to be an extremely difficult challenge and has become a topic of an extensive research effort. While no method for designing an xe2x80x9coptimalxe2x80x9d interleaver has yet been found, most of the published procedures for designing a good interleaver are based on the following principles:
a. Given the size of the data block and other parameters of the turbo coding scheme, design an interleaver by either applying a deterministic procedure or by generating numerous random permutations and picking out the xe2x80x9cbestxe2x80x9d permutation. The choice of the best permutation is made by applying some quality criterion.
b. Store the found interleaver in the transmitter (encoder) and in the receiver (decoder). The interleaver is usually stored as the sequence of the permuted indices. Thus, the required storage memory increases linearly with the block size K.
The foregoing approach for xe2x80x9coff-linexe2x80x9d construction of an interleaver enables one to generate an interleaver matched to a specific coding scheme by applying one of the suggested procedures. However, this approach implies that memory storage is allocated in both the transmitter and the receiver for storing the computed permutation.
The foregoing approach for xe2x80x9coff-linexe2x80x9d construction of an interleaver has two shortcomings:
a. Dedicated storage memory is required. This might be a serious problem if the coding scheme operates with a large block.
b. The approach is not applicable for a coding system which is designed to use blocks of variable size. If the number of legitimate block sizes is large, it would be impractical to design and store xe2x80x9coff-linexe2x80x9d designed interleavers for all allowable block sizes.
Dolinar et al, Weight Distribution of Turbo Codes Using Random and Nonrandom Permutations, JPL TDA Progress Report 42-122 (August 1995) analyzes various interleavers with regard to how effectively data sequences that produce low encoded weight at the output of one encoder are matched with permutations of the same data sequence that yield higher encoded weights at the outputs of the other encoder(s). One of the permutations considered (in detail for the case N=32) was the circular shift xcfx80(j)=a*j+r (mod N) where r less than N is an offset and a  less than N is a step size that is relatively prime to N. Similarly, Takeshita et al, On Deterministic Linear Interleavers for Turbo Codes, 35th Allerton Conference on Communication, Control and Computing (September 1997). Divsalar et al, U.S. Pat. No. 6,023,783 illustrates various Turbo code encoder architectures which incorporate interleavers.
The present invention provides a permutation generator for constructing interleavers for turbo coding schemes with varying block sizes.
This has advantages including real-time permutation generation with minimal memory requirements.